import numpy as np


def left_min_dq(prices):
    """
    实现股票买卖问题的时间复杂度O(n)线性时间算法，该算法原由浙江工业大学2015届学生严凡提出
    :param prices: 每日股票价格数据
    :return: 最佳买入价格，最佳卖出价格，最佳收益
    """
    left_min = prices[0]
    len_prices = len(prices)
    left_min_buy_array = np.zeros_like(prices)
    for i in range(len_prices):
        key = prices[i]
        if key <= left_min:
            left_min = key
        left_min_buy_array[i] = left_min
    diff_array = prices - left_min_buy_array  # 利润差值数组
    max_diff = np.max(diff_array)  # 最大利润差值
    index = np.where(diff_array == max_diff)  # 最大利润差值索引
    max_buy, max_sell = left_min_buy_array[index][0], prices[index][0]
    return max_buy, max_sell, max_diff


if __name__ == '__main__':
    stock_prices = np.array([13, 17, 15, 8, 14, 15, 19, 7, 8, 9])
    print(left_min_dq(stock_prices))
